/**
 * 
 */
package process;

import java.util.Vector;

import util.Timer;

import data.SimilaritySet;

/**
 * TagSkyline use the skyline method to retrieve the correlated tags of a target tag
 * @author yexijiang
 * @date Jul 8, 2008
 */
public class TagSkyline 
{

	private SimilaritySet[] m_Sets;
	private Vector<String>[] m_SetsLabels;
	private int m_Dimension;
	private Vector<Vector<String>>[] m_Clusters;
	
	
	public TagSkyline(int numOfCandidateTags, int sequence[], int recordsForEachTag)
	{
		PreProcess pre = new PreProcess(numOfCandidateTags, sequence, recordsForEachTag);
		m_Dimension = sequence.length;
		m_Sets = pre.preProcess();
		m_SetsLabels = new Vector[m_Sets.length];
		for(int i = 0; i < m_SetsLabels.length; ++i)
		{
			m_SetsLabels[i] = m_Sets[i].getKeys();
		}
		m_Clusters = new Vector[m_Sets.length];
	}
	
	/**
	 * Test if v1 dominate v2
	 * @param v1	the possible dominate vector
	 * @param v2	the possible vector been dominated
	 * @return	whether v1 dominate v2
	 */
	private boolean dominant(Vector<Double> v1, Vector<Double> v2)
	{
		boolean larger = false;	//	record if exists a larger value
		if(v1.size() != v2.size())
		{
			try {
				throw new Exception("Two vector size not equal.");
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		
		for(int i = 0; i < v1.size(); ++i)
		{
			if(!larger)
				if(v1.get(i) > v2.get(i))
				{
					larger = true;
				}
			if(v1.get(i) < v2.get(i))	//	there exists one dimension that v1 < v2
				return false;
		}
		
		if(larger)	//	there exists one dimension that v1 > v2 and remain dimension no less than v2
			return true;
		
		return false;
	}
	
	/**
	 * K-Dominant. Defined in "Finding k-Dominant Skylines in High Dimensional Space". If k set to the 
	 * dimension of the vector, then it becomes the dominant algorithm.
	 * @param v1	the first vector
	 * @param v2	the second vector
	 * @param k		the value of k
	 * @return	whether v1 k-dominant v2
	 */
	private boolean k_Dominant(Vector<Double> v1, Vector<Double> v2, int k)
	{
		int count = 0;
		boolean larger = false;
		
		if(v1.size() != v2.size())
		{
			try {
				throw new Exception("Two vector size not equal.");
			} catch (Exception e) {
				e.printStackTrace();
			}
		}
		
		for(int i = 0; i < v1.size(); ++i)
		{
			if(!larger)
				if(v1.get(i) > v2.get(i))
				{
					larger = true;
				}
			if(v1.get(i) >= v2.get(i))
				++count;
		}
		
		if(larger && count >= k)	//	if k-dominate
			return true;
		
		return false;
	}
	
	/**
	 * Two scan algorithm in "Finding k-Dominant Skylines in High Dimensional Space".
	 * @param setNo	the index of the set
	 * @param kDom	the k value
	 */
	public Vector<String> twoScanAlgorithm(int setNo, int kDom)
	{
		//	presort of the dataset
		double sum[] = new double[m_Sets[setNo].size()];
		for(int i = 0; i < sum.length; ++i)
		{
			Vector<Double> record = m_Sets[setNo].getRecordByKeys(m_SetsLabels[setNo].get(i));
			sum[i] = 0.0;
			for(int j = 0; j < m_Dimension; ++j)
			{
				sum[i] += record.get(j);
			}
		}
		
		Vector<String> R = new Vector<String>();
		
		//	first scan
		for(int i = 0; i < m_Sets[setNo].size(); ++i)
		{
			boolean isDominate = true;
			String recName1 = m_SetsLabels[setNo].get(i);
			Vector<Double> v1 = m_Sets[setNo].getRecordByKeys(recName1);
			for(int j = 0; j < R.size(); ++j)
			{
				Vector<Double> v2 = m_Sets[setNo].getRecordByKeys(R.get(j));
				if(k_Dominant(v2, v1, kDom))
					isDominate = false;
				if(k_Dominant(v1, v2, kDom))
					R.remove(j);
			}
			if(isDominate)
				R.add(recName1);
		}
		
		//	second scan
		for(int i = 0; i < m_Sets[setNo].size(); ++i)
		{
			String recName1 = m_SetsLabels[setNo].get(i);
			Vector<Double> v1 = m_Sets[setNo].getRecordByKeys(recName1);
			for(int j = 0; j < R.size(); ++j)
			{
				String recName2 = R.get(j);
				Vector<Double> v2 = m_Sets[setNo].getRecordByKeys(R.get(j));
				if(recName1.equals(recName2))	//	v1 != v2
					continue;
				if(k_Dominant(v1, v2, kDom))
					R.remove(j);
			}
		}
		
		for(int i = 0; i < R.size(); ++i)
		{
			m_Sets[setNo].removeRecord(R.get(i));
			for(int j = 0; j < m_SetsLabels[setNo].size(); ++j)
			{
				if(m_SetsLabels[setNo].get(j).equals(R.get(i)))
				{
					m_SetsLabels[setNo].remove(j);
					break;
				}
			}
		}
		return R;
	}
	
	public Vector<Vector<String>> skylineClustering(int setNo, int kDom)
	{
		Vector<Vector<String>> clusters = new Vector<Vector<String>>();
		
		int i = 0;
		while(m_Sets[setNo].size() > 0)	//	while there exists any points
		{
			Vector<String> cluster = twoScanAlgorithm(setNo, kDom);
			clusters.add(cluster);
		}
		
		return clusters;
	}
	
	/**
	 * Do skyline clustering to all the sets
	 * @return TODO
	 */
	public Vector<Vector<String>>[] skylineClusteringAll()
	{
		System.out.println("Begin skyline clustering.");
		long startSkylineClustering = Timer.startRecord();
		for(int i = 0; i < m_Sets.length; ++i)
		{
			Vector<Vector<String>> skyline = skylineClustering(i, m_Dimension);
			m_Clusters[i] = skyline;
		}
		long endSkylineClustering = Timer.endRecord(startSkylineClustering);
		System.out.println("End skyline clustering, cost time " + endSkylineClustering + ".");
		return m_Clusters;
	}
	
	public Vector<String> getTargetTags()
	{
		Vector<String> targetTags = new Vector<String>();
		for(int i = 0; i < m_Sets.length; ++i)
		{
			targetTags.add(m_Sets[i].getTargetTag());
		}
		return targetTags;
	}
	
	public String toString()
	{
		String msg = new String();
		
		for(int i = 0; i < m_Sets.length; ++i)	//	for each set
		{
			Vector<Vector<String>> skylineClusters = m_Clusters[i];
			System.out.println("\nFor tag '" + m_Sets[i].getTargetTag() + "':");
			for(int j = 0; j < skylineClusters.size(); ++j)
			{
				System.out.println("\n\tFor cluster " + j + ":");
				Vector<String> cluster = skylineClusters.get(j);
				for(int k = 0; k < cluster.size(); ++k)
				{
					System.out.print("\t\t" + cluster.get(k));
				}
			}
		}
		
		return msg;
	}
	
	public static void main(String[] args)
	{
		int numOfCandidateTags = 100;
		int sequence[] = {1,2,3,4,5,6,7,8};
		int recordsForEachTag = 10;
		for(int i = 0; i < 10; ++i)
		{
			numOfCandidateTags = (i + 1) * 100;
			System.out.println("Experiment " + (i + 1) + ":");
			TagSkyline skyline = new TagSkyline(numOfCandidateTags, sequence, recordsForEachTag);
			skyline.skylineClusteringAll();
			//System.out.println(skyline);
		}
	}
	
}
